//
// Created by francklinson on 2021/7/25 AT 22:17.
//
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        int ans = nums[0];
        int former = nums[0];
        int cur = 0;
        for (int i = 1; i < nums.size(); ++i) {
            cur = max(former + nums[i], nums[i]);
            ans = max(ans, cur);
            former = cur;
        }
        return ans;
    }
};

int main() {
    vector<int> nums{-2, 1, -3, 4, -1, 2, 1, -5, 4};
    Solution solution;
    cout << solution.maxSubArray(nums) << endl;
    return 0;
}

